Let E be an elliptic curve defined over a finite field Fq, corresponding to the finite field with q elements, where q=pm, with p being a prime number and m being an integer greater than or equal to one. A base point P belonging to this curve (i.e. the base point PεE(Fq)), is deemed to have an order equal to n.
Before using such an elliptic curve in cryptographic applications, it is appropriate to verify several parameters (cf. §4.2 of document A1 entitled: “Guide to elliptic curve cryptography” by D. Hankerson et al.) ensuring the security of such a curve. Among these parameters, the cofactor h of such an elliptic curve verifying the following equation: h=#E(Fq)/n (where #E(Fq) corresponds to the cardinal of the elliptic curve) must be determined in order especially to prevent attacks of the “small subgroup attacks” type (cf. §4.3 of document A1). Indeed, when the cofactor h of an elliptic curve is great, the curve potentially has a weakness because of the possibility of attacks of the “small subgroup attack” being carried out. In addition, the cofactor h of an elliptic curve is increasingly being used to specify novel cryptographic protocols (such as for example the ECC CDH (Elliptic Curve Cryptography Cofactor Diffie-Hellman) protocol. Other examples of applications are described in “Recommendation for Pair-Wise Key Establishment Schemes Using Discrete Logarithm Cryptography” (the reference of this document is: NIST SP800-56A), and in the document “Supplemental Access Control for Machine Readable Travel Documents (v. 1.01)” published by the ICAO (International Civil Aviation Organization).
However, determining the cofactor of an elliptic curve within an electronic component such as a microcontroller of a smart card is not easy. This is because the techniques for determining the cardinal of an elliptic curve are costly (in terms of complexity of the computing operations to be carried out). This point is mentioned in §4.2.3 of the document A1, in relation to the use, for example, of a technique developed by Satoh as well as variants such as the algorithm called the SST (Satoh-Skjemaa-Taguchi) algorithm or the AGM (arithmetic geometric mean) algorithm.
From this prior-art document, there is a known solution using the inequality of the Hasse theorem which, when n>4√q, proposes a more precise technique, that is, we have: h=floor((√q+1)2/n) where the function floor(·) corresponds to the function called an integer part.
Thus, determining the cofactor in this example necessitates determining the square root of q.
To determine the square root of q, those skilled in the art would have used one of the techniques described in the documents U.S. Pat. No. 6,389,443, U.S. Pat. No. 6,625,632 and U.S.-2006/0059216, which propose techniques for determining a square root to determine the value of the cofactor.
However, one drawback of these methods for determining square roots is that they are costly to implement and that, in addition, they necessitate modifications in an electronic component such as a microcontroller of a smart card that has to implement the determining of a cofactor.